package org.cabbage.lintcode;

/**
 * 合并两个排序的整数数组A和B变成一个新的数组 mdzz
 * 给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]
 *
 * @author gezhangyuan
 */
public class MergeSortedArray {

    public static void main(String[] args) {
        int[] c = mergeSortedArray(new int[]{1, 2, 3, 4}, new int[]{2, 4, 5, 6});
        for (int ci : c) {
            System.out.println(ci);
        }
    }

    public static int[] mergeSortedArray(int[] A, int[] B) {

        int[] c = new int[A.length + B.length];


        int ta = 0;
        int tb = 0;
        int tc = 0;
        int va = A[0];
        int vb = B[0];
        ;
        while (tc < A.length + B.length - 1) {
            while (ta <= A.length - 1 && (A[ta] <= vb || tb >= B.length - 1)) {
                c[tc] = A[ta];
                va = A[ta];
                tc++;
                ta++;
            }
            while (tb <= B.length - 1 && (va > B[tb] || ta == A.length - 1)) {
                c[tc] = B[tb];
                vb = B[tb];
                tc++;
                tb++;
            }
        }

        return c;
    }
}
